<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /**
       * 思路：
       *  通过二维数组实现
       * 循环数组每一项，然后在倒着循环二维数组每一项
       * 跟二维数组每一项数组的最后一个进行比较，如果大于最后一个数字，就给当前项的下一项添加一个新的二位数组并把 n 添加到数组末尾
       * 特殊情况：如果循环结束没有找到大于当前 n 的末尾数组，就把二维数组第一项改为 [[n]]
       * 至此循环结束二维数组最后一个数组的内容就是“最长递增子序列了”
       * **/
      function LIS(arr) {
        if (arr.length === 0) {
          return [];
        }
        const result = [[arr[0]]];

        for (i = 1; i < arr.length; i++) {
          const n = arr[i];
          _update(n);
        }

        function _update(n) {
          for (let i = result.length - 1; i >= 0; i--) {
            const arr = result[i];
            const tail = arr[arr.length - 1];
            if (n > tail) {
              result[i + 1] = [...arr, n];
              return;
            }
          }
          result[0] = [n];
        }
        console.log(result);

        return result[result.length - 1];
      }

      console.log(LIS([4, 5, 1, 2, 7, 3, 6, 9]));
    </script>
  </body>
</html>
